package com.njupt.graphTheory;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/4/16 21:57
 * @Description: dijkstra（朴素版）
 * @Version: 1.0
 */


public class KaMaDijkstra_47 {


    public static void main(String[] args) {
//        int M = Integer.MAX_VALUE;
//        int n = 7;
//        int[][] graph = {{M,M,M,M,M,M,M,M}
//                        ,{M,M,1,4,M,M,M,M}
//                        ,{M,M,M,2,5,M,4,M}
//                        ,{M,M,M,M,2,M,M,M}
//                        ,{M,M,M,M,M,3,M,M}
//                        ,{M,M,M,M,M,M,M,4}
//                        ,{M,M,M,M,M,M,M,9}
//                        ,{M,M,M,M,M,M,M,M}};
//        7 9
//        1 2 1
//        1 3 4
//        2 3 2
//        2 4 5
//        3 4 2
//        4 5 3
//        2 6 4
//        5 7 4
//        6 7 9

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        sc.nextLine();
        int[][] graph = new int[N + 1][N + 1];
        for (int i = 0; i <= N ; i++) {
            Arrays.fill(graph[i],Integer.MAX_VALUE);
        }

        for (int i = 0; i < M; i++) {
            int i1 = sc.nextInt();
            int i2 = sc.nextInt();
            int val = sc.nextInt();
            sc.nextLine();
            graph[i1][i2] = val;

        }

        int start = 1;
        int end = N;

        int[] minDist = new int[N + 1];
        Arrays.fill(minDist,Integer.MAX_VALUE);
        minDist[start] = 0;

        boolean[] isVisited = new boolean[N + 1];
        Arrays.fill(isVisited,false);

        int[] parent = new int[N + 1];
        Arrays.fill(parent,-1);

        dijkrastra(N,graph,minDist,isVisited,parent);

        if(minDist[end] == Integer.MAX_VALUE){
            System.out.println(-1);
        }else{
            System.out.println(minDist[end]);
        }

        StringBuilder sb = new StringBuilder();
        sb.append(end);
        sb.insert(0,"->");
        for(int i = end;i > 2;i= parent[i]){
            sb.insert(0,parent[i]);
            sb.insert(0,"->");
        }
        sb.insert(0,parent[2]);
        System.out.println(sb.toString());
    }

    private static void dijkrastra(int n,int[][] graph, int[] minDist, boolean[] isVisited,int[] parent ) {

        //1、遍历所有的节点
        for (int i = 1; i <= n ; i++) {

            //2、选择距离源点最近且未被访问过的节点，作为逻辑源点（源点到该节点的最短路径）
            int min_dest = Integer.MAX_VALUE;
            int curSource = 1;

            for(int v = 1 ; v <= n;v++){

                if(!isVisited[v] && minDist[v] < min_dest){
                    min_dest = minDist[v];
                    curSource = v;
                }
            }
            isVisited[curSource] = true;

            //3、计算逻辑源点相邻的节点，根性经过逻辑源点之后能访问到的节点，跟新这些节点到源点的最短路径
            for (int v = 1; v <= n ; v++) {
                if(!isVisited[v]){
                    if(graph[curSource][v] != Integer.MAX_VALUE
                            && (minDist[curSource] + graph[curSource][v] < minDist[v])){
                        minDist[v] = minDist[curSource] + graph[curSource][v];
                        parent[v] = curSource;
                    }
                }
            }
        }






    }
}
